import java.util.*;

/**
 * @author LKQ
 * @date 2022/4/15 15:15
 * @description 二分查找
 */
public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] w = {1,2,3,1,1};
        solution.shipWithinDays(w, 4);
    }
    public int shipWithinDays(int[] weights, int days) {
        int sum = 0;
        int max = 0;
        for (int w: weights) {
            sum += w;
            if (w > max) {
                max = w;
            }
        }
        // 由于包裹不能拆分，那么船的最低运载能力，即二分左边界为最大的包裹重量，右边界即为全部包裹重量。
        int l = max, r = sum, ans = -1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (check(weights, mid, days)) {
                ans = mid;
                r = mid - 1;
            }else {
                l = mid + 1;
            }
        }
        return ans;
    }

    private boolean check(int[] weights, int mid, int days) {
        int need = 1;
        int sum = 0;
        for (int w: weights) {
            if (sum + w > mid) {
                ++need;
                sum = 0;
            }
            sum += w;
        }
        return need <= days;
    }
}
